package leetcode.code0375;

public class Solution3752 {

	private Integer[][] dp;

	public int getMoneyAmount(int n) {
		dp = new Integer[n + 1][n + 1];
		return this.f(1, n);
	}

	// 在[l,r]范围内，随便选择一个数尝试，返回最小代价
	private int f(int l, int r) {
		if (l >= r) {
			return 0;
		}
		int ans = Integer.MAX_VALUE;
		for (int i = l; i <= r; i++) {// 当前选i，即以i为左右树的头
			int left = this.f(l, i - 1);// 左子树的最小代价
			int right = this.f(i + 1, r);// 右子树的最小代价
			int cur = Math.max(left, right) + i;// 在经历左右最小代价情况下，最大的是选i不得不承受的`痛`
			ans = Math.min(ans, cur);// [l,r]范围内所有`痛`中最小的，是f的最小代价
		}
		dp[l][r] = ans;
		return ans;
	}

	public static void main(String[] args) {
		Solution3752 so = new Solution3752();
		int ans = so.getMoneyAmount(22);
		System.out.println(ans);
	}
}
